package com.zdp.algorithm.stackandqueue;

import lombok.extern.slf4j.Slf4j;

import java.util.Stack;

/**
 * @author zhengdp
 * @Description 最大子矩阵的大小
 * @Date 2023/1/11 22:12
 * @Created by zhengdp
 */
@Slf4j
public class MaxRecSize {
    private static int[][] map = new int[][] {
            {1,0,1,1},{1,1,1,1},{1,1,1,0}
    };
    public static void main(String[] args) {
        MaxRecSizeImpl impl = new MaxRecSizeImpl();
        log.info("impl1 {}",impl.maxRecSize(new int[][] {
                {0,0,1},{1,1,1}
        }));

        MaxRecSizeImpl2 impl2 = new MaxRecSizeImpl2();
        log.info("impl2 {}",impl2.maximalRectangle(new String[]{"001","111"}));
    }
}

class MaxRecSizeImpl {

    /**
     * 从上到下，分割行，以每一行为底，计算该行上每一列上的连续1的数量 , 得到 int[] height
     * 去每个 height 进行计算，得到以该行为底时，最大的子矩阵大小
     * @param map 矩阵
     * @return 最大子矩阵大小
     */
    public int maxRecSize(int[][] map ) {
        int[] height = new int[map[0].length];
        int max = Integer.MIN_VALUE ;
        for(int i = 0 ; i < map.length ; i ++) {
            for(int j = 0; j < map[i].length ; j ++) {
                height[j] = map[i][j] == 0 ? 0 : height[j] + 1;
            }
            max = Math.max(max,maxRecFromBottom(height));
        }
        return max;
    }


    /**
     * 以 heigh 为底，获取到最大的子矩阵大小
     * height 可以看成是一个柱状图，我们需要求得每个柱子可以向外扩张到哪里。
     * 柱子左右扩展何时结束，取决于其何时遇到比它小的柱子。
     * 也就是说，我们要求每个柱子左右的最近且比他小的柱子的位置。
     * 得到这个位置后，我们就可以得到以该柱子为中心，最大可以扩张的子矩阵长度了，高度自然就是该柱子的高度。
     * 也就是说，我们得到 [left ,right] ==> 可以圈定范围  range : right - left +1
     * 【求最近且小于的柱子，使用单调栈即可 ==> 见 {@link MonotonicStack}】
     * @param height 以某行为底，每列的最大高度 （连续1）
     * @return 最大子矩阵大小
     */
    public int maxRecFromBottom(int[] height) {
        int max = Integer.MIN_VALUE;
        // 单调队列，求最近的比较小的元素，所以栈顶到栈底应该是单调递减的
        Stack<Integer> monotonicStack = new Stack<>();
        for(int i = 0; i < height.length ; i ++ ) {
            int temp = height[i];
            while(!monotonicStack.isEmpty() && height[monotonicStack.peek()] > temp) {
                // 满足 左右两边最小的条件
                int top = monotonicStack.pop();
                int left = monotonicStack.isEmpty() ? -1 : monotonicStack.peek();
                int range = (i -1) - (left  + 1) + 1;
                int curArea = range * height[top];
                max = Math.max(curArea,max);
            }
            monotonicStack.push(i);
        }
        while(!monotonicStack.isEmpty()) {
            int top = monotonicStack.pop();
            // 此时留在栈中的元素，其右侧都没有比他小的值，也就是说，他们可以扩充到数组的最后
            int right = height.length;
            int left = monotonicStack.isEmpty() ? -1 : monotonicStack.peek();
            int range = (right-1) - (left + 1) +1;
            int curArea = range * height[top];
            max = Math.max(curArea,max);
        }
        return max;
    }
}

class MaxRecSizeImpl2 {
    public int maximalRectangle(String[] matrix) {
        if(matrix.length == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int[] height = new int[matrix[0].length()];
        for(int i = 0 ; i< matrix.length ; i ++ ) {
            String temp = matrix[i];
            for(int j = 0 ; j< temp.length() ; j ++ ) {
                char c = temp.charAt(j);
                height[j] =  c == '0' ? 0 : height[j] +1;
            }
            max = Math.max(max,getMax(height));
        }
        return max;
    }

    private int getMax(int[] height) {
        int max = Integer.MIN_VALUE;
        // 单调队列，求最近的比较小的元素，所以栈顶到栈底应该是单调递减的
        Stack<Integer> monotonicStack = new Stack<>();
        for(int i = 0; i < height.length ; i ++ ) {
            int temp = height[i];
            while(!monotonicStack.isEmpty() && height[monotonicStack.peek()] > temp) {
                // 满足 左右两边最小的条件
                int top = monotonicStack.pop();
                int left = monotonicStack.isEmpty() ? -1 : monotonicStack.peek();
                int range = (i -1) - (left  + 1) + 1;
                int curArea = range * height[top];
                max = Math.max(curArea,max);
            }
            monotonicStack.push(i);
        }
        while(!monotonicStack.isEmpty()) {
            int top = monotonicStack.pop();
            int left = monotonicStack.isEmpty() ? -1 : monotonicStack.peek();
            int range = (height.length -1 ) - (left + 1) +1;
            int curArea = range * height[top];
            max = Math.max(curArea,max);
        }
        return max;
    }
}
